package be.ac.ulb.mlg.utils.measure;

/*
 * The MIT License (MIT)
 * 
 * Copyright (c) 2013 Jean-Sebastien Lerat (Jean-Sebastien.Lerat@ulb.ac.be)
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/**
 * 
 * @author Jean-Sebastien Lerat (Jean-Sebastien.Lerat@ulb.ac.be)
 * @version 1.00, 24/06/2013
 * @see <a href="http://dx.doi.org/10.1093%2Fbiomet%2F30.1-2.81">A New Measure of Rank Correlation (Kendall, M)</a>
 */

import static java.lang.Math.exp;
import static java.lang.Math.abs;
import static java.lang.Math.log;

import be.ac.ulb.mlg.utils.Measure;
import be.ac.ulb.mlg.utils.MeasureUtils;

/**
 * Using Tau-b (adjustments for ties)
 * Knight's Algorithm
 */
public class Kendall implements Measure{
	@Override
	public double measure(final double[] A, final double[] B,boolean[] computable){
		final double[] rankA	= new double[A.length];
		final double[] rankB	= new double[B.length];
		
		final int n1 = MeasureUtils.naturalRank(computable,A,rankA);
		final int n2 = MeasureUtils.naturalRank(computable,B,rankB);
		
		int n0=0, n3=0, t3=0;
		final double upperBounds = A.length + 1;
		int index;

		if(computable != null){
			int previous;
			for(previous=0;previous < computable.length && !computable[previous]; previous++){
				rankA[previous] = rankB[previous] = Double.NEGATIVE_INFINITY;
			}
			if(previous >= computable.length) return ERROR_VALUE;//if previous is not < computable.length => all is NaN
			rankA[previous] = rankA[previous] * upperBounds  + rankB[previous];
			++n0;
			for(index=previous+1;index<computable.length;index++)
				if(computable[index]){
					rankA[index] = rankA[index] * upperBounds  + rankB[index];
					if(abs(rankA[index]-rankA[previous])<1e-14){
						t3++;
					}else{
						n3 += t3*(t3+1);
						t3  = 0;
					}
					++n0;
					previous = index;
				}else{
					rankA[index] = rankB[index] = Double.NEGATIVE_INFINITY;
				}
		}else{
			rankA[0] = rankA[0] * upperBounds  + rankB[0];
			for(index=1;index<A.length;index++){
				rankA[index] = rankA[index] * upperBounds  + rankB[index];
				if(abs(rankA[index]-rankA[index-1])<1e-14){
					t3++;
				}else{
					t3  = 0;
				}
			}
			n0 = A.length;
		}
		n3 += t3*(t3+1);
		n3 >>= 1;
		n0 = (n0 * (n0-1)) >> 1;

		MeasureUtils.bubbleSort(rankA, rankB);

		final int swap = MeasureUtils.countSwap(rankB);
		
		final double numerator		= n0 + ( -n1-n2+n3 - (swap<<1));//nc -nd = n0 - n1 - n2 + n3 - 2*S(y) 
		final double denominator	= exp(0.5*(log(n0-n1)+log(n0-n2)));//underflow (Numerical Analysis course) ( exp(0.5*log(x)) <=> sqrt(x) )
		
		if(denominator<1e-16)return ERROR_VALUE;
		
		return numerator/denominator;
	}
//	
//	private static int mergesortCounting(double[] comparable){
//		int index,leftTape,rightTape,end;
//		int ptrLeftTape,ptrRightTape,position;
//		
//		int[] swapper = new int[comparable.length];
//		int swapCount = 0;
//		
//		for(int tapeSize = 1; tapeSize < comparable.length; tapeSize <<= 1){
//			for(index = 0; index < comparable.length; index += tapeSize<<1){
//				leftTape	= index;
//				rightTape	= min(index+tapeSize,comparable.length);
//				end			= min(rightTape+tapeSize,comparable.length);
//				
//				ptrLeftTape		= leftTape;
//				ptrRightTape	= rightTape;
//
//				for(position = leftTape; position < end; position++){
//					if(ptrLeftTape >= rightTape){
//						swapper[position]	=  toSort[ptrRightTape++];
//						swapCount			+= rightTape - ptrLeftTape;
//					}else if(ptrRightTape < end
//							//&& toSort[ptrLeftTape] > 0 && toSort[ptrRightTape] > 0
//							&& comparable[toSort[ptrLeftTape]] > comparable[toSort[ptrRightTape]]){
//						swapper[position]	=  toSort[ptrRightTape++];
//						//if(computable[toSort[ptrLeftTape]] && computable[toSort[ptrRightTape-1]])
//						swapCount += rightTape - ptrLeftTape;
//					}else{
//						swapper[position] = toSort[ptrLeftTape++];
//					}
//					/*
//					// this is the detailed version condition by condition of the algorithm
//					if(ptrLeftTape<rightTape){
//						//left tape are not yet ended
//						if(ptrRightTape<end){
//							//the right tape is not ended, we must still choose between the right and the left elements
//							if(toSort[ptrLeftTape] > toSort[ptrRightTape]){
//								//the left element is greater than the right
//								//copy the right element before the left (the right and increase the ptr of the right)
//								swapper[position]	=  toSort[ptrRightTape++];
//								swapCount			+= rightTape - ptrLeftTape;
//							}else{
//								//the left element is already smaller than the right.
//								//just copy it
//								swapper[position] = toSort[ptrLeftTape++];
//							}
//						}else{
//							//right tape processing ended, just copy the left tape
//							swapper[position] = toSort[ptrLeftTape++];
//						}
//					}else{
//						//left tape processing ended, just copy the right tape (right tape is logically ended)
//						swapper[position] = toSort[ptrRightTape++];
//					}*/
//				}
//				
//			}
//			
//			final int[] tmp	= toSort;
//			toSort		= swapper;
//			swapper	= tmp;
//		}
//		
//		return swapCount;
//	}
	
	
	 
	@Override
	public boolean hasNativeImplementation() {
		return true;
	}
	@Override
	public boolean requireDataTransformation() {
		return false;
	}

	@Override
	public void transform(double[][] data) {
		//nothnig to do
	}
}
